\section{Algorithm}\label{sec:algo}

\subsection{Main Algorithm}
\label{sec:main}

The nature of our algorithm is such that we {\em continuously} maintain an approximation to the densest subgraph in the dynamic network. At any time, after a short initialization period, any node knows whether it is a member of the output subgraph of our algorithm. In this section, we give the description of the algorithm and fully specify the behavior of each of the nodes in the network. The analysis of the running time and the approximation guarantees are deferred to the following sections.

Our main protocol for maintaining a dense subgraph is given in Algorithm~\ref{algo:maintain}. It maintains a family of  $p=O(\log_{1+\epsilon} n)$ candidates for the densest subgraph, along with an approximation of the number of nodes and edges in each graph. The algorithm works in phases in which it estimates the size of the current subgraph $V_j$ and the number of edges in it using the algorithms discussed in the following subsection. At the end of the phase it computes the next subgraph $V_{j+1}$ using a criterion in Line 9 of Algorithm~\ref{algo:maintain} (explained further in Section~\ref{sec:approx}). After $p$ such rounds, the algorithm has all the information it needs to output an approximation to the densest subgraph. This process is repeated continuously, and the solution is computed from the last complete family of graphs (i.e., complete computation of $p$ subgraphs). 

\begin{algorithm}[h]
\caption{{\sc Maintain}($\epsilon$)}
\label{algo:maintain}

{\bf Input:} $\epsilon>0$

{\bf Output:} The algorithm maintains a family of sets of nodes $\mathcal{F}=\{V_0, V_1, \ldots, V_p\}$ where $V_0=V(G)$, $V_i\subseteq V_{i-1}$ for all $i$ and $p=O(\log_{1+\epsilon} n)$. It also maintains $\cR=\{(m_0, n_0), (m_1, n_1), \ldots, (m_p, n_p)\}$ where each $m_i$ and $n_i$ are supposed to be the approximated number of edges and nodes, respectively, of the subgraph of $G_t$ (the current graph) induced by $V_i$. At all times, each node knows which subgraphs in $\cal F$ it is in and all numbers in $\cR$.

%(We might want to state this as a lemma.)  This family has the following property. Let $t$ be any time after the first time all $V_1, \ldots, V_p$ are first computed. For any $V'\subseteq V$, let $\rho_t(V')$ be the density of the subgraph of $G_t$ induced by $V'$. Let
%%
%$$V_{\cF}^k=\arg\max_{V_i\in \cF,\ |V_i|\geq k} r_i\,.$$
%%
%Then, $V_{\cF}^k$ is a good approximation of the densest subgraph of $G_t$ of size at least $k$, i.e.,
%%Let $H_i$ be the subgraph of $G_t$ induced by $V_i$. For any $k$,
%%$$\max_{V_i\in \mathcal{F}, |V_i|\geq k} \rho(H_i)\in [(1-\epsilon)\rho(G_{t}), (1+\epsilon)\rho(G_{t})]\,.$$
%%
%$$\rho_t(V_{\cF}^k)\geq (1-\epsilon) \max_{V'\subseteq V(G_t), |V'|\geq k} \rho_t(V')\,.$$
%%
%It also maintains the approximated optimal density: Let $i^*$ be such that $V_{i^*}=V_{\cF}^k$. Then,
%$$m_{i^*}/n_{i^*} \in \rho_t(V_{\cF}^k)\,.$$
%
%%{\bf (Make sure the number is correct!!!)}.
%
%%{\bf Output:} Let $t^*$ be the time the algorithm ends. The algorithm outputs a family of subgraphs $\mathcal{F}=\{H_0, H_1, \ldots, H_p\}$ where $H_0=G$, $G_i\subseteq G_{i-1}$ for all $i$ and $p=O(\log_{1+\epsilon} n)$ such that, for any $k$, $\max_{G_i\in \mathcal{F}} \rho(H_i)\in [\frac{1}{\alpha\beta}\rho(G_{t^*}), \alpha\beta\cdot\rho(G_{t^*})]${\bf (Make sure the number is correct!!!)}. (Each node knows which subgraphs in $\cal F$ it is in and the density of {\em all} subgraphs in $\cal F$.)

\begin{algorithmic}[1]

\STATE Let $\delta=\epsilon/24$.

\STATE Let $j = 0$. Let $V_0=V$ (i.e., we mark every node as in $V_0$).


\REPEAT

\STATE Compute $n_j$, the $(1+\delta)$-approximation of $|V_j|$ (i.e., $(1+\delta)|V_j|\geq n_j\geq (1-\delta)|V_j|$). In the end of the algorithm every node knows $n_j$. See Algorithms~\ref{algo:kuhn} and~\ref{algo:count nodes} for detailed implementation.


\IF{$n_j=0$}

\STATE Let $j = 0$. %Let $V_0=V$ (i.e., we mark every node as in $V_0$).
(Note that we do not recompute $n_0$.)

\ENDIF

\STATE Let $G_t$ be the network in the beginning of this step. Let $H_t$ be the subgraph of $G_t$ induced by $V_{j}$. We compute $m_{j}$, the $(1+\delta)$-approximation of the number of edges in $H_t$ (i.e., $(1+\delta)|E(H_t)|\geq m_{j}\geq (1-\delta)|E(H_t)|$). In the end of the algorithm every node knows $m_{j}$. See Algorithm~\ref{algo:count edges} for detailed implementation.

%\STATE Let $\Delta=m_{j}/n_{j}$.


\STATE Let $G_{t'}$ be the network in the beginning of this step.  Let $H_{t'}$ be the subgraph of $G_{t'}$ induced by $V_{j}$. Let $V_{j+1}$ be the set of nodes in $V_{j}$ whose degree in $H_{t'}$ is at most $(1+\delta)m_j/n_j$. In the end of this step, every node knows whether it is in $V_{j+1}$ or not. This step can be done in one round since every node already knows $m_{j}/n_{j}$ and can easily check, in one round, the number of neighbors in $G_{t'}$ that are in $V_{j}$.

%\STATE Compute $n_j$, the $(1+\epsilon)$-approximation of $|V_j|$ (i.e., $(1+\epsilon)|V_j|\geq n_0\geq (1-\epsilon)|V_j|$). In the end of the algorithm every node knows $n_0$. See Algorithm~\ref{algo:count nodes} for detailed implementation.

\STATE Let $j=j+1$.


\UNTIL{forever}


\end{algorithmic}
\end{algorithm}


At any time, the densest subgraph can be computed using the steps outlined in Algorithm~\ref{algo:densest}. This procedure works simply by picking the subgraph with the highest density, taking into account the possibility that the size of this subgraph may be less than $k$. If the graph turns out to be less than size $k$, we pad it by having the rest of the nodes run a distributed procedure to elect appropriately many nodes to add to the subgraph and get its size up to at least $k$. 

Any time a densest subgraph query is initiated in the network, the nodes simply run Algorithm~\ref{algo:densest} based on the subgraphs continuously being maintained by Algorithm~\ref{algo:maintain}, and compute which of them are in the approximation solution. At the end of this query, each nodes is aware of whether it is in the approximate densest subgraph or not. 


\begin{algorithm}
\caption{{\sc Densest Subgraph}($k$)}
\label{algo:densest}

{\bf Input:} $k$, the parameter for the densest at-least-$k$ subgraph problem

%Let $t$ be the time the algorithm ends. Needed now?

{\bf Output:} The algorithm outputs a set of nodes $V_i\cup\hat{V}$ (every node knows whether it is in $\hat{V}$ or not) such that $|V_i\cup\hat{V}|\geq k$ that is supposed to be the approximated at-least-$k$ densest subgraph along with its approximated density.

%such that
%$$\rho_t(V')\geq (1-\epsilon) \max_{V'\subseteq V(G_t), |V'|\geq k} \rho_t(V')\,$$
%as well as its approximated density
%$r'\in \rho_t(V_{\cF}^k)\,.$
%Moreover, it outputs the approximated density of $\rho_t(V')$, $r'=\geq [(1-\epsilon)\rho_k(G_{t^*}), (1+\epsilon)\rho_k(G_{t^*})]$ where $\rho_k(G_{t^*})$ is the density of the densest subgraph of $G_{t^*}$ of size at least $k$.

\begin{algorithmic}[1]
%\STATE Simply output $V_{\cF}^k=\arg\max_{V_i\in \cF,\ |V_i|\geq k} r_i\,.$ and its corresponding approximated density $m_{i^*}/n_{i^*}$.
\STATE Let $i=\max_{i} m_i/\max(k, n_i)\,.$
%\STATE Let $V_{out}$ be the set of all nodes in $V_i$ (each node knows whether it is in $V'$ or not)
\IF{$n_i<(1+\delta)k$}
\STATE Let $\Delta=(1+\delta)k-n_i$. (Every node can compute $\Delta$ locally.)
%et $V'$ be the set of nodes obtained by adding arbitrary $\ell$ nodes in $V\setminus V_i$ to $V_i$, where $(1+\delta)k-n_i\leq \ell\leq (1+\delta)((1+\delta)k-n_i)$  as follows.
\REPEAT
\STATE Every node not in $V_i$ locally flips a coin which is head with probability $\Delta/n_0$.
\STATE Let $\hat{V}$ be the set of nodes whose coins return heads.
\STATE Approximately count the number of nodes in $\hat{V}$ using the algorithm discussed in Section~\ref{sec:counting} with error parameter $\epsilon=\delta$. Let $\Delta'$ be the result. (Note that $\Delta'/(1+\delta)\leq |\hat{V}|\leq (1+\delta)\Delta'$ with high probability.)
\UNTIL{$(1+\delta)\Delta\leq \Delta'\leq (1+2\delta)\Delta$}
\ENDIF
\RETURN $V_i\cup \hat{V}$
\end{algorithmic}
\end{algorithm}

\subsection{Approximating the number of nodes and edges}\label{sec:counting}

Our algorithms make use of an operation in which the number of nodes and edges in a given subgraph need to be computed. We achieve this in $O(D)$ rounds using a modified version of an algorithm from~\cite{KuhnLO10}. Their algorithm allows for approximate counting of the size of a dynamic network. We modify it to work for any subgraph that we are interested in. We also show how it can be used to approximate the number of edges in this subgraph at a given time. In the interest of space, these results can be found in Appendix~\ref{sec:count}.

% \input{count}

%\subsection{Padding nodes}
%
%
%\begin{algorithm}
%\caption{{\sc Padding}($t$, $\epsilon$)}
%\label{algo:padding}
%
%{\bf Input:} $p$, the number of nodes to be selected, and $\epsilon$, the error parameter
%
%{\bf Output:} $p'$ nodes will be selected (each node knows whether it is selected or not) where $p\leq p'\leq (1+\epsilon)p$.
%
%%such that
%%$$\rho_t(V')\geq (1-\epsilon) \max_{V'\subseteq V(G_t), |V'|\geq k} \rho_t(V')\,$$
%%as well as its approximated density
%%$r'\in \rho_t(V_{\cF}^k)\,.$
%%Moreover, it outputs the approximated density of $\rho_t(V')$, $r'=\geq [(1-\epsilon)\rho_k(G_{t^*}), (1+\epsilon)\rho_k(G_{t^*})]$ where $\rho_k(G_{t^*})$ is the density of the densest subgraph of $G_{t^*}$ of size at least $k$.
%
%\begin{algorithmic}[1]
%%\STATE Simply output $V_{\cF}^k=\arg\max_{V_i\in \cF,\ |V_i|\geq k} r_i\,.$ and its corresponding approximated density $m_{i^*}/n_{i^*}$.
%\STATE Let $i=\max_{i} m_i/\max{k, n_i}\,.$
%\STATE If $n_i<(1+\delta)k$ then let $V'$ be the set of nodes obtained by adding arbitrary $(1+\delta)k-n_i$ nodes in $V\setminus V_i$ to $V_i$, as follows.
%\STATE EXPLAIN THE PADDING ALGORITHM HERE.
%\RETURN $V'$
%\end{algorithmic}
%\end{algorithm}
